package 题目集.图.最短路;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//https://pintia.cn/problem-sets/1739473818167930880/exam/problems/1739473861503483916?type=7&page=0
public class 天梯地图 {
    public static void main(String[] args) {
        Reader sc = new Reader();
        int n = sc.nextInt();
        int m = sc.nextInt();
        Graph graph = new Graph(n);
        while (m-- > 0) {
            int[] edge = {sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt()};
            graph.insert(edge);
        }
        Node s = graph.nodes.get(sc.nextInt());
        Node e = graph.nodes.get(sc.nextInt());
        LinkedList<Integer> timePath=new LinkedList<>();
        LinkedList<Integer> lenPath=new LinkedList<>();
        LinkedList<Node> byTime = getByTime(graph, s, e);
        LinkedList<Node> byLen= getByLen(graph, s, e);
        int time=byTime.getLast().time;
        int len=byLen.getLast().len;
        for (Node node : byTime) {
            timePath.add(node.id);
        }
        for (Node node : byLen) {
            lenPath.add(node.id);
        }
        StringBuilder builder=new StringBuilder();
        if (lenPath.equals(timePath)){
            builder.append("Time = ").append(time).append("; Distance = ").append(len).append(": ");
            for (Integer i : lenPath) {
                builder.append(i).append(" => ");
            }
            System.out.println(builder.substring(0,builder.length()-4));
        }else {
            builder.append("Time = ").append(time).append(": ");
            for (Integer i : timePath) {
                builder.append(i).append(" => ");
            }
            System.out.println(builder.substring(0,builder.length()-4));
            builder=new StringBuilder();
            builder.append("Distance = ").append(len).append(": ");
            for (Integer i : lenPath) {
                builder.append(i).append(" => ");
            }
            System.out.println(builder.substring(0,builder.length()-4));
        }
    }

    //dj
    public static LinkedList<Node> getByTime(Graph graph, Node s, Node e) {
        NodHeap<Node> heap = new NodHeap<>(graph.nodes.size());
        heap.setComparator((old, young) -> {
            if (old.time == young.time) {
                return old.len > young.len;
            }
            return old.time > young.time;
        });
        heap.setUpdater((old, young) -> {
            old.time=young.time;
            old.len= young.len;;
        });
        Node info = new Node(-1);
        heap.addOrUpdateOrIgnore(s, info, null);
        while (heap.isNotEmpty()) {
            Node curr = heap.pop();
            if (curr == e) break;
            for (Edge edge : curr.edges) {
                info.len = curr.len + edge.len;
                info.time = curr.time + edge.time;
                heap.addOrUpdateOrIgnore(edge.to, info, edge.from);
            }
        }
        return heap.preList(e);
    }
    public static LinkedList<Node> getByLen(Graph graph, Node s, Node e) {
        NodHeap<Node> heap = new NodHeap<>(graph.nodes.size());
        heap.setComparator((old, young) -> {
            if (old.len == young.len) {
                return old.pass > young.pass;
            }
            return old.len > young.len;
        });
        heap.setUpdater((old, young) -> {
            old.len= young.len;;
            old.pass=young.pass;
        });
        Node info = new Node(-1);
        heap.addOrUpdateOrIgnore(s, info, null);
        while (heap.isNotEmpty()) {
            Node curr = heap.pop();
            if (curr == e) break;
            for (Edge edge : curr.edges) {
                info.len = curr.len + edge.len;
                info.pass = curr.pass + 1;
                heap.addOrUpdateOrIgnore(edge.to, info, edge.from);
            }
        }
        return heap.preList(e);
    }


    static class Graph {
        Map<Integer, Node> nodes = new HashMap<>();

        public Graph(int n) {
            for (int i = 0; i < n; i++) {
                nodes.put(i, new Node(i));
            }
        }

        public void insert(int[] edge) {
            Node from = nodes.get(edge[0]);
            Node to = nodes.get(edge[1]);
            from.edges.add(new Edge(from, to, edge[3], edge[4]));
            if (edge[2] == 0)
                to.edges.add(new Edge(to, from, edge[3], edge[4]));
        }
    }

    static class Node {
        int id;

        public Node(int id, int len, int time, int pass) {
            this.id = id;
            this.len = len;
            this.time = time;
            this.pass = pass;
        }

        public Node(int id) {
            this.id = id;
        }

        int len;
        int time;
        int pass;
        List<Edge> edges = new ArrayList<>();

        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    ", len=" + len +
                    ", time=" + time +
                    ", pass=" + pass +
                    '}';
        }
    }

    static class Edge {
        Node from;
        Node to;
        int len;
        int time;

        public Edge(Node from, Node to, int len, int time) {
            this.from = from;
            this.to = to;
            this.len = len;
            this.time = time;
        }
    }
    static class NodHeap<T> {
        private Map<T, Integer> indexMap;
        private Map<T, T> preMap;
        private T[] heap;
        private int heapSize = 1;
        private NodHeap.MyComparator<T> comparator;
        private NodHeap.MyUpdater<T> updater;

        /**
         * node:原节点
         * info:走另一条路线的信息
         */
        public void addOrUpdateOrIgnore(T node, T info, T pre) {
            Integer i = indexMap.get(node);
            if (i != null) {    //堆中存在node的情况
                if (comparator.compare(node, info)) {    //是否需要更新
                    insert(node,info,pre,i);
                    sink(i);
                }
                return;
            }
            insert(node,info,pre,heapSize++);
        }

        /**
         * 更新node的索引、前缀、以及信息
         */
        public void insert(T node,T info,T pre,int i){
            heap[i]=node;
            indexMap.put(node,i);
            preMap.put(node,pre);
            updater.update(node,info);
            rise(i);
        }
        public T pop() {
            T pop = heap[1];
            swap(1, --heapSize);
            sink(1);
            return pop;
        }
        public NodHeap(int size) {
            indexMap = new HashMap<>(size);
            preMap = new HashMap<>(size);
            this.heap = (T[]) new Object[size + 1];   //0位置弃而不用
        }

        public void swap(int a, int b) {
            T node = heap[a];
            heap[a] = heap[b];
            heap[b] = node;
            indexMap.put(heap[a], a);
            indexMap.put(heap[b], b);
        }

        /**
         * 从指定位置向上升起
         */
        public void rise(int i) {
            while (i != 1) {  //不是根节点
                int parent = i >> 1;
                if (!comparator.compare(heap[parent], heap[i])) {   //无需上升
                    break;
                }
                swap(parent, i);
                i = parent;
            }
        }

        /**
         * 从指定位置向下沉
         */
        public void sink(int i) {
            while (!isLeaf(i)) {     //并非叶子节点
                int child = topChild(i);
                if (!comparator.compare(heap[i], heap[child])) {   //当前节点是最小的，无需下沉
                    break;
                }
                swap(i, child);
                i = child;
            }
        }

        public int topChild(int i) {
            int l = i << 1;
            int r = i << 1 | 1;
            if (r >= heapSize) {
                return l;
            }
            if (comparator.compare(heap[l], heap[r])) {
                return r;
            }
            return l;
        }

        public boolean isLeaf(int i) {
            return i << 1 >= heapSize;
        }

        public LinkedList<T> preList(T o) {
            LinkedList<T> list = new LinkedList<>();
            while (o != null) {
                list.addFirst(o);
                o = preMap.get(o);
            }
            return list;
        }
        public boolean isNotEmpty(){
            return heapSize>1;
        }

        public static void main(String[] args) {
            NodHeap<Integer> nodHeap = new NodHeap<Integer>(3);
            nodHeap.setComparator(((old, young) -> {
                return young > old;
            }));
            System.out.println();
        }

        public void setUpdater(NodHeap.MyUpdater<T> updater) {
            this.updater = updater;
        }

        public void setComparator(NodHeap.MyComparator<T> comparator) {
            this.comparator = comparator;
        }

        public interface MyComparator<T> {
            boolean compare(T old, T young);
        }

        public interface MyUpdater<T> {
            void update(T old, T young);
        }
    }
    static class Reader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {    //内存中没有
                String nextLine = innerNextLine();
                if (nextLine == null) {     //且没有下一行
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);  //读入一行
            }
            return true;
        }

        public String nextLine() {
            tokenizer = new StringTokenizer("");    //清空内存中的字符
            return innerNextLine();
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}
